
#include <iostream>
#include <assert.h>

using namespace std;

namespace my_list
{
    template<class T>
    struct __list_node
    {
        T _data;
        __list_node<T>* _prev;
        __list_node<T>* _next;

        __list_node(const T& x = T())
            :_data(x)
             ,_prev(nullptr)
             ,_next(nullptr)
        {}
    };

    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_node<T> Node;
        typedef __list_iterator<T, Ref, Ptr> iterator;

        __list_iterator(Node* node)
            :_node(node)
        {}

        bool operator!=(const iterator& it) const 
        {
            return _node != it._node;
        }
        bool operator==(const iterator& it) const 
        {
            return _node == it._node;
        }

        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &(operator*());
        }

        iterator& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        iterator& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        iterator operator+(size_t n)
        {
            iterator tmp(*this);

            while (n -- )
            {
                ++ tmp;
            }

            return tmp;
        }
        iterator operator-(size_t n)
        {
            iterator tmp(*this);

            while (n -- )
            {
                -- tmp;
            }

            return tmp;
        }

        Node* GetNode()
        {
            return _node;
        }
    
    private:
        Node* _node;

    };

    template<class T>
    class list 
    {
        typedef __list_node<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;

        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        const_iterator begin() const 
        {
            return const_iterator(_head->_next);
        }
        const_iterator end() const 
        {
            return const_iterator(_head);
        }

        void Init_head()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        list()
        {
            Init_head();
        }

        ~list()
        {
            clear();

            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();

            while (it != end())
            {
                it = erase(it);
            }
        }

        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            Init_head();

            while (first != last)
            {
                push_back(*first);
                ++ first;
            }
        }

        void swap(list<T>& l)
        {
            ::swap(_head, l._head);
        }

        list(const list<T>& lt)
        {
            Init_head();

            list<T> tmp(lt.begin(), lt.end());
        
            swap(tmp);
        }

        void push_back(const T& x)
        {
            //Node* newnode = new Node(x);
            //Node* tail = _head->_prev;
            //tail->_next = newnode;
            //newnode->_prev = tail;
            //newnode->_next = _head;
            //_head->_prev = newnode;
            
            insert(end(), x);
        }

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        void pop_back()
        {
            erase(-- end());
        }

        void pop_front()
        {
            erase(begin());
        }

        iterator insert(iterator pos, const T& x)
        {
            Node* newnode = new Node(x);
            Node* cur = pos.GetNode();
            Node* prev = cur->_prev;

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            assert(pos != end());

            Node* cur = pos.GetNode();
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            delete cur;

            prev->_next = next;
            next->_prev = prev;

            return iterator(next);
        }

        bool empty()
        {
            return begin() == end();
        }

    private:
        Node* _head;
    };
    
    class A
    {
    public:
        void print()
        {
            cout << _a << ' ' << _b;
        }

        A(int a = 0, int b = 0)
        {
            _a = a;
            _b = b;
        }

        int _a;
        int _b;
    };

    void test1()
    {
        list<A> lt;
        lt.push_back(A(10, 20));
        lt.push_back(A(11, 21));
        lt.push_back(A(12, 22));
        lt.push_back(A(13, 23));
        lt.push_back(A(14, 24));

        list<A>::iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << it->_a << ' ' << it->_b << endl;
            ++ it;
        }
        cout << endl;

    }

    void test2()
    {
        list<int> l1;

        l1.push_back(1);
        l1.push_back(2);
        l1.push_back(3);
        l1.push_back(4);
        l1.push_back(5);
        l1.push_back(6);
        l1.push_back(7);
        l1.push_back(8);

        list<int>::iterator it = l1.begin();

        while (it != l1.end())
        {
            cout << *it << ' ';
            ++ it;
        }
        cout << endl;
        
        l1.insert(l1.begin() + 3, 999);
        
        it = l1.begin();
        while (it != l1.end())
        {
            cout << *it << ' ';
            ++ it;
        }
        cout << endl;
    }

    void test3()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_front(4);
        lt.push_front(6);
        lt.push_front(12);
        lt.push_back(15);
        lt.push_front(4);
        lt.push_front(8);
        lt.push_back(5);
        lt.push_back(7);
        lt.push_front(10);
        lt.push_back(2);

        auto it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << ' ';
            ++ it;
        }
        cout << endl;

        list<int> l1(lt);

        auto it1 = l1.begin();
        while (it1 != l1.end())
        {
            cout << *it1 << ' ';
            ++ it1;
        }
        cout << endl;
    }

}
